/*
 * Package il.ac.biu.cs.grossmm.impl.activeData
 * File LinkedNodeset.java
 * 
 * This is a part of presence service framework prototype. 
 * See javadoc for more information.
 *  
 * Copyright (C) 2006 Grossmann Mark
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.

 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

package il.ac.biu.cs.grossmm.impl.activeData;

import il.ac.biu.cs.grossmm.api.data.UpdateType;

/**
 * Implementation of nodeset based on linked lists
 */
public class LinkedNodeset<N> {
	boolean even;

	LinkedNode<N> u0, c0, a0, r0; // 4*4=16 bytes

	LinkedNode<N> u1, c1, a1, r1; // 4*4=16 bytes

	LinkedNode rootNode;

	LinkedNode parentNode;

	int parentIndex;

	public LinkedNodeset(LinkedNode parent, int i) {
		this.parentNode = parent;
		this.rootNode = (LinkedNode) parent.getRoot();
		this.parentIndex = i;
	}

	LinkedNode<N> insert(LinkedNode<N> head, LinkedNode<N> node) {
		if (even) {
			if (head == null) {
				// first node in the list
				node.next0 = node.prev0 = node;
			} else {
				// at least second node in the list
				node.next0 = head;
				node.prev0 = head.prev0;
				node.prev0.next0 = node;
				head.prev0 = node;
			}
		} else {
			if (head == null) {
				// first node in the list
				node.next1 = node.prev1 = node;
			} else {
				// at least second node in the list
				node.next1 = head;
				node.prev1 = head.prev1;
				node.prev1.next1 = node;
				head.prev1 = node;
			}
		}

		return node;
	}

	LinkedNode<N> remove(LinkedNode<N> node) {
		LinkedNode<N> prev;
		LinkedNode<N> next;

		// node.parentSet = null; // removed.

		if (even) {
			prev = node.prev0;
			if (prev == node) {
				return null; // the only node in the list
			}

			next = node.next0;

			prev.next0 = next;
			next.prev0 = prev;
		} else {
			prev = node.prev1;
			if (prev == node)
				return null;

			next = node.next1;

			prev.next1 = next;
			next.prev1 = prev;
		}

		return next;
	}

	LinkedNode<N> append(LinkedNode<N> firstList, LinkedNode<N> secondList) {
		LinkedNode<N> firstTail, secondTail;

		if (firstList == null)
			return secondList;

		if (secondList == null)
			return firstList;

		if (even) {
			firstTail = firstList.prev0;
			secondTail = secondList.prev0;

			firstList.prev0 = secondTail;
			secondTail.next0 = firstList;

			secondList.prev0 = firstTail;
			firstTail.next0 = secondList;
		} else {
			firstTail = firstList.prev1;

			secondTail = secondList.prev1;

			firstList.prev1 = secondTail;
			secondTail.next1 = firstList;

			secondList.prev1 = firstTail;
			firstTail.next1 = secondList;
		}

		return firstList;
	}

	void add(LinkedNode<N> node) {
		if (even)
			a0 = insert(a0, node);
		else
			a1 = insert(a1, node);

		node.newUpdType = UpdateType.ADDED;

		parentNode.changed();
	}

	void moveTo(LinkedNode<N> node, UpdateType u) {
		assert node.newUpdType != u;

		LinkedNode<N> head = remove(node);

		switch (node.newUpdType) {
		case UNCHANGED:
			if (even)
				u0 = head;
			else
				u1 = head;
			break;
		case CHANGED:
			if (even)
				c0 = head;
			else
				c1 = head;
			break;
		case ADDED:
			if (even)
				a0 = head;
			else
				a1 = head;
			break;
		default:
			assert false;
		}

		switch (u) {
		case ADDED:
			if (even)
				a0 = insert(a0, node);
			else
				a1 = insert(a1, node);
			break;
		case REMOVED:
			if (even)
				r0 = insert(r0, node);
			else
				r1 = insert(r1, node);
			break;
		case CHANGED:
			if (even)
				c0 = insert(c0, node);
			else
				c1 = insert(c1, node);
			break;
		case UNCHANGED:
			if (even)
				u0 = insert(u0, node);
			else
				u1 = insert(u1, node);
			break;
		}

		parentNode.changed();
	}

	/*
	 * Emulation of lambda-function in java... Ugly, but that's it.
	 */
	interface Lambda {
		void doIt(LinkedNode n);
	}

	static class DoShift implements Lambda {
		public void doIt(LinkedNode n) {
			n.shift();
		}
	}

	static final Lambda DO_SHIFT = new DoShift();

	static class DoShift2 implements Lambda {
		public void doIt(LinkedNode n) {
			n.shift2();
		}
	}

	static final Lambda DO_SHIFT2 = new DoShift2();

	static class DoCheckShift2 implements Lambda {
		public void doIt(LinkedNode n) {
			if (n.curUpdType != UpdateType.UNCHANGED)
				n.shift2();
		}
	}

	static final Lambda DO_CHECK_SHIFT2 = new DoCheckShift2();

	void forEach(boolean stage, LinkedNode list, Lambda lambda) {
		if (list == null)
			return;

		LinkedNode n = list;

		// the condition check is moved out of the loop for speed optimization
		if (stage) {
			do {
				lambda.doIt(n);
				n = n.next0;
			} while (n != list);
		} else {
			do {
				lambda.doIt(n);
				n = n.next1;
			} while (n != list);
		}
	}

	public void shift() {
		// shift values in all subtrees
		if (even) {
			forEach(even, u0, DO_CHECK_SHIFT2);
			forEach(even, c0, DO_SHIFT);
			forEach(even, a0, DO_SHIFT);
			forEach(even, r0, DO_SHIFT); // can be optimized (need to shift
			// 1->0 only)
		} else {
			forEach(even, u1, DO_CHECK_SHIFT2);
			forEach(even, c1, DO_SHIFT);
			forEach(even, a1, DO_SHIFT);
			forEach(even, r1, DO_SHIFT);
		}

		// swap lists
		even = !even;

		// append c-list and a-list to u-list, clear c-list and a-list
		if (even) {
			u0 = append(u0, c0);
			c0 = null;
			u0 = append(u0, a0);
			a0 = null;
			r0 = null;
		} else {
			u1 = append(u1, c1);
			c1 = null;
			u1 = append(u1, a1);
			a1 = null;
			r1 = null;
		}

		LinkedNode<N> aList = even ? a1 : a0;

		// add all nodes in a-list of the previous epoch to u-list of the next
		// epoch
		a: if (aList != null) {
			LinkedNode<N> n = aList;
			LinkedNode<N> next, prev;
			next = even ? u0 : u1;

			if (next == null) {
				// u-list is empty

				next = prev = n;

				// add the first element from the odd a-list (=n)
				// to the even u-list. shift to the next element
				// in the odd a-list
				if (even) {
					u0 = n;
					n.next0 = n.prev0 = n;
					n = n.next1;
				} else {
					u1 = n;
					n.next1 = n.prev1 = n;
					n = n.next0;
				}

				if (n == aList)
					break a;
			} else
				prev = even ? next.prev0 : next.prev1;

			do {
				if (even) {
					n.prev0 = prev;
					prev.next0 = n;

					prev = n;
					n = n.next1;
				} else {
					n.prev1 = prev;
					prev.next1 = n;

					prev = n;
					n = n.next0;
				}
			} while (n != aList);

			if (even) {
				prev.next0 = next;
				next.prev0 = prev;
			} else {
				prev.next1 = next;
				next.prev1 = prev;
			}
		}

		// remove all nodes in r-list of the previous epoch from the current
		// epoch
		LinkedNode<N> rList = even ? r1 : r0;

		if (rList != null) {
			LinkedNode<N> n = rList;

			do {
				if (even)
					u0 = remove(n);
				else
					u1 = remove(n);

				n = even ? n.next1 : n.next0;
			} while (n != rList);
		}

	}

	public void clear() {
		// TODO Implement clear
		// 
		// throw new RuntimeException("Not implemented");
	}

	/**
	 * Shift epochs for all subnodes of a node which changed between the old and
	 * the current epochs (0) and did not change between the current and the new
	 * epochs (1).
	 * 
	 */
	public void shift2() {

		// all subnodes of this node did not change in (even)
		// shift-2 all nodes changed in (odd)

		forEach(!even, even ? c1 : c0, DO_SHIFT2);
		forEach(!even, even ? a1 : a0, DO_SHIFT2);
	}
}
